#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <cstdlib>

typedef int SeqListType;

typedef struct SeqList
{
    SeqListType *a;
    int size;
    int capacity;
} SeqList;

void SeqListInit(SeqList *ps)
{
    assert(ps);
    ps->a = nullptr;
    ps->size = ps->capacity = 0;
}

void SeqListDestory(SeqList *ps)
{
    assert(ps);
    free(ps->a);
    ps->a = nullptr;
    ps->size = ps->capacity = 0;
}

void SeqListPrint(SeqList *ps)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SeqListCheckCapacity(SeqList *ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SeqListType *New = (SeqListType *)realloc(ps->a, newcapacity * sizeof(int));
        if (New == nullptr)
        {
            printf("realloc fail!");
            return;
        }

        ps->a = New;
        ps->capacity = newcapacity;
    }
}


void SeqListInsert(SeqList *ps, int pos, SeqListType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);

    for(int i = ps->size; i >= 0; i--)
    {
        ps->a[i] = ps->a[i-1];
    }
    ps->a[pos] = x;
    ps->size++;
}

void SeqListPushFront(SeqList *ps, SeqListType x)
{
    // assert(ps);
    // SeqListCheckCapacity(ps);
    // for (int i = ps->size; i >= 0; i--)
    // {
    //     ps->a[i] = ps->a[i-1];
    // }

    // ps->a[0] = x;
    // ps->size++;

    SeqListInsert(ps, 0, x);
}


void SeqListPushBack(SeqList* ps, SeqListType x)
{
    // assert(ps);
    // SeqListCheckCapacity(ps);
    // ps->a[ps->size] = x;
    // ps->size++;
    SeqListInsert(ps, ps->size, x);
}


void SeqListErase(SeqList* ps, int pos)
{
    assert(ps);
    assert(ps->size > 0);
    assert(pos >= 0 && pos < ps->size);
    for(int i = pos; i <= ps->size-1; i++)
    {
        ps->a[i] = ps->a[i+1];
    }
    ps->size--;
}

void SeqListPopFront(SeqList* ps)
{
    // assert(ps);
    // assert(ps->size > 0);

    // for(int i = 0; i <= ps->size; i++)
    // {
    //     ps->a[i] = ps->a[i+1];
    // }
    // ps->size--;

    SeqListErase(ps, 0);
}

void SeqListPopBack(SeqList* ps)
{
    // assert(ps);
    // assert(ps->size > 0);
    // ps->size--;
    SeqListErase(ps, ps->size-1);
}


int SeqListFind(SeqList* ps, SeqListType x)
{
    assert(ps);
    for(int i = 0; i < ps->size; i++)
    {
        if(ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

void SeqListModify(SeqList* ps, int pos, SeqListType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size-1);
    ps->a[pos] = x;
}

int main()
{
    SeqList* a = new SeqList;
    SeqListInit(a);
    SeqListInsert(a, 0, 1);
    SeqListInsert(a, 0, 2);
    SeqListInsert(a, 0, 3);
    SeqListPrint(a);
    SeqListDestory(a);
    return 0;
}